#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef int ElemType;
typedef struct BSTNode {
    ElemType key;
    struct BSTNode *lchild, *rchild;
} BSTNode, *BSTree;

// 在二叉排序树t中查找关键字为key的结点，递归实现
BSTNode * SearchBST(BSTNode *T, ElemType key) {
    if (!T) {
        return NULL;    // 遇到空树，直接结束
    }
    if (T->key == key) {
        return T;       // 若根节点关键字和key相等，返回根节点
    }
    if (T->key > key) {
        return SearchBST(T->lchild, key);   // 去左子树找
    }
    return SearchBST(T->rchild, key);       // 去右子树找
}

// 在二叉排序树t中查找关键字为key的结点，非递归实现
BSTNode * SearchBST2(BSTNode *T, ElemType key) {
    BSTNode *p = T;
    while (p != NULL && p->key != key) {
        if (p->key > key) {
            p = p->lchild;  // 在左子树中查找
        } else {
            p = p->rchild;  // 在右子树中查找
        }
    }
    if (p->key == key) {
        return p;   // 成功找到
    }
    else return NULL;
}

// 在二叉排序树t中插入一个关键字为key的结点，递归实现
void InsertBST(BSTNode **T, ElemType key) {
    BSTNode *x;
    x = (BSTNode *)malloc(sizeof(BSTNode)); // 创建一个新节点
    x->key = key;                       // 初始化结点
    x->lchild = x->rchild = NULL;
    if(*T==NULL)    *T = x;
    else{
        if((*T)->key==key) {        // 结点已存在
            free(x);
            return;
        }
        else if(key<(*T)->key) {
            InsertBST(&(*T)->lchild, key);  // 插入到左子树中
        }
        else {
            InsertBST(&(*T)->rchild, key);  // 插入到右子树中
        }
    }
}

// 在二叉排序树t中插入一个关键字为key的结点，非递归实现
void InsertBST2(BSTNode **T, ElemType key) {
    BSTNode *x, *p, *q;
    x = (BSTNode *)malloc(sizeof(BSTNode));  // 创建一个新节点
    x->key = key;                       // 初始化结点
    x->lchild = x->rchild = NULL;
    
    if (*T == NULL)     *T = x;
    else{
        p = *T;
        while (p!=NULL) {
            if (p->key == key)      return ;  // 如果关键字已存在，插入失败
            q = p;
            if (p->key > key) {
                p = p->lchild;  // 在左子树中查找
            } else {
                p = p->rchild;  // 在右子树中查找
            }
        }
        if (q->key > key) {
            q->lchild = x;
        } else {
            q->rchild = x;
        }
    }
}

// 中序遍历二叉排序树t
void PrintBST(BSTree t) {
    if (t) {
        PrintBST(t->lchild);
        printf("%d ", t->key);
        PrintBST(t->rchild);
    }
}